/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package classes;

import java.awt.Polygon;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.io.*;

/**
 *
 * @author Filippo
 * questa è la classe vera e propria che risolve l'algoritmo
 */
public class voronoidiagram implements Algorithm {
    
    public int dimensionex;
    public int dimensioney;
    
            //oggetto di tipo Data da fornire come risultato
    public Data result = new Data();
        
        //creo un poligono vuoto (uso la classe java presistente) e gli passo i punti del poligono in input prelevandoli da d (DataIn input)
    public Polygon poligono1=new Polygon();
        
        
    public int minX = 0;
    public int minY = 0;
    public int maxX = 0;
    public int maxY = 0;
        
    public int numpoints;
    public int[] x;
    public int[] y;
    
    /* i tre generatori iniziali  */
    public vertice p1 = new vertice((float) 0.5, (float) (3.0*Math.sqrt(2.0)/2.0 + 0.5), 1);
    public vertice p2 = new vertice((float)(-3.0*Math.sqrt(6.0)/4.0 + 0.5),(float)( -3.0*Math.sqrt(2.0)/4.0 + 0.5), 1);
    public vertice p3 = new vertice((float)(3.0*Math.sqrt(6.0)/4.0 + 0.5),(float)( -3.0*Math.sqrt(2.0)/4.0 + 0.5), 1);
    
    public ArrayList <vertice> generators = new ArrayList<vertice>();
    public ArrayList <vertice> vertices = new ArrayList<vertice>();
    public ArrayList <lato> edges = new ArrayList<lato>();
    public ArrayList <poligono> polygons = new ArrayList<poligono>();
    public ArrayList <lato> deledges = new ArrayList<lato>();
    
    //da cancellare, debug;
        
        //int[] xmod = new int[] {350,22,600};
        //int[] ymod = new int[] {427,22,70};
    
    public quaternarytree qtree;
    
    voronoidiagram(int x,int y){
    this.dimensionex =x;
    this.dimensioney =y;
    this.maxX = dimensionex;
    this.maxY = dimensioney;
    }
    
    public boolean getConvex(){return true;}
    
    public float getdistance(vertice p1, vertice p2){
    
        return (float) Math.sqrt(((p1.x - p2.x) * (p1.x - 
		p2.x)) + ((p1.y - p2.y) * (p1.y - p2.y)));
    }
    
    public float mapvaluetozerooneinterval(float value, float minvalue, float maxvalue) {
    
        if (minvalue == maxvalue) return 0;
	float factor = (value - minvalue) / (maxvalue - minvalue);
	return factor;
    }
    
    public float calcposx(float x){ return this.dimensionex * x; }
    
    public float calcposy(float y){ return this.dimensioney * y; }
    
    //implementazione vera e propria dell'algoritmo, prende un Data in ingresso
    public Data execute(Data d) {
        
        poligono1=(Polygon) d.getShapes().get(0);

        
        //estraggo i vettori di punti per entrambe le coordinate
        x = poligono1.xpoints;
        y = poligono1.ypoints;
        
        
           
        //estraggo il numero di vertici totali
        numpoints=poligono1.npoints;
        
        
        
        this.render();

        
        
    return result;
    }
    
    public void render(){
    
        /*grafo iniziale formato dai soli 3 vertici*/
        createseedgraph();
        
        /*ottieni il vertice nel centro del cerchio
         * che circoscrive i tre punti iniziali*/
        createfirstvertex();
        
        /*closed curve che circonda il grafo "aumentato"*/
        createinfinitevertices();
        
        /*crea la wingededge secondo l'algoritmo descritto in spatial tess.*/
        createwingededge();
        
        /*pulisci l'array prima di iniziare*/
        this.vertices.clear();
        
        this.generators.clear(); // ?
        
        int i = 0;
        
        this.generators.ensureCapacity(numpoints+10);
        
        
        do {
        
            float xcoord = x[i];
            float ycoord = y[i];
            
            xcoord = mapvaluetozerooneinterval(xcoord, this.minX, this.maxX);
            ycoord = mapvaluetozerooneinterval(ycoord, this.minY, this.maxY);
            
            vertice v = new vertice();
            v.x = xcoord;
            v.y = ycoord;
            v.w = 1;
            
            this.generators.add(i, v);
            i++;
        }
        while (i < this.numpoints);
        
        qtree = new quaternarytree(generators, p1);
        
        
        
        populatediagram();
        printdiagram();
        
    }

    public void createseedgraph() {
        
        generators.add(0, p1);
        generators.add(1, p2);
        generators.add(2, p3);
    }

    public void createfirstvertex() {
        
        vertice centre = new vertice();
        if (getcentre(centre)==true){
        
            vertice v = new vertice();
            v.x = centre.x;
            v.y = centre.y;
            v.w = 1;
            
            this.vertices.add(0, v);
        }
    }

    public boolean getcentre(vertice centre) {
        
        boolean resultbool = true;
        float x1, y1, ma, mb, nx1, nx2, nx3, ny1, ny2, ny3;
        
        ma=mb=0;
        nx1 = this.p1.x; 
        nx2 = this.p2.x; 
        nx3 = this.p3.x;
        ny1 = this.p1.y;
        ny2 = this.p2.y;
        ny3 = this.p3.y;
        
        if (nx1 != nx2)
            ma = (ny2 - ny1) / (nx2 - nx1);
        else
            resultbool = false;

        if (nx2 != nx3)
            mb = (ny3 - ny3) / (nx3 - nx2);
        else
            resultbool = false;

        if ((ma == 0) && (mb == 0))
            resultbool = false;

        if (ma == mb)
            resultbool = false;

        if (resultbool == true)
            {
		x1 = (ma * mb * (ny1 - ny3) + mb * (nx1 + nx2) - ma * (nx2 + nx3)) / (2 * (mb - ma));
			
		if (ma != 0)
                    y1 = -(x1 - (nx1 + nx2) / 2) / ma + (ny1 + ny2) / 2;
		else
                    y1 = -(x1 - (nx2 + nx3) / 2) / mb + (ny2 + ny3) / 2;
			
                    centre.x = x1;
                    centre.y = y1;
	}
        return resultbool;
    }

    public void createinfinitevertices() {
        
        addseedvertex(this.p1,this.p3);
        addseedvertex(this.p2,this.p3);
        addseedvertex(this.p1,this.p2);
        
    }

    public void addseedvertex(vertice c1, vertice c2) {
        
        float midx, midy;
        float centrex = this.vertices.get(0).x;
        float centrey = this.vertices.get(0).y;
        float lenght;
        
        midx = (float) ((c1.x + c2.x) / 2.0);
        midy = (float) ((c1.y + c2.y) / 2.0);
        
        lenght = (float) (Math.sqrt(((midx - centrex) * (midx - centrex)) + ((midy - centrey) * (midy - centrey))));
        
        vertice v = new vertice();
        v.x = (midx - centrex) / lenght;
        v.y = (midy - centrey) / lenght;
        v.w = 0;
        
        this.vertices.add(v);
        
    }

    public void createwingededge() {
        
        createedges();
        createpolygons();
        createvertices();
        
        this.edges.get(0).cwpredecessor = this.edges.get(2);
        this.edges.get(0).ccwpredecessor = this.edges.get(1);
        this.edges.get(0).cwsuccessor = this.edges.get(4);
        this.edges.get(0).ccwsuccessor = this.edges.get(3);
        this.edges.get(0).leftpolygon = this.polygons.get(1);
        this.edges.get(0).rightpolygon = this.polygons.get(0);
        
        this.edges.get(1).cwpredecessor = this.edges.get(0);
        this.edges.get(1).ccwpredecessor = this.edges.get(2);
        this.edges.get(1).cwsuccessor = this.edges.get(5);
        this.edges.get(1).ccwsuccessor = this.edges.get(4);
        this.edges.get(1).leftpolygon = this.polygons.get(2);
        this.edges.get(1).rightpolygon = this.polygons.get(1);
        
        this.edges.get(2).cwpredecessor = this.edges.get(1);
        this.edges.get(2).ccwpredecessor = this.edges.get(0);
        this.edges.get(2).cwsuccessor = this.edges.get(3);
        this.edges.get(2).ccwsuccessor = this.edges.get(5);
        this.edges.get(2).leftpolygon = this.polygons.get(0);
        this.edges.get(2).rightpolygon = this.polygons.get(2);
        
        this.edges.get(3).cwpredecessor = this.edges.get(5);
        this.edges.get(3).ccwpredecessor = this.edges.get(2);
        this.edges.get(3).cwsuccessor = this.edges.get(0);
        this.edges.get(3).ccwsuccessor = this.edges.get(4);
        this.edges.get(3).leftpolygon = this.polygons.get(0);
        this.edges.get(3).rightpolygon = this.polygons.get(3);
        
        this.edges.get(4).cwpredecessor = this.edges.get(3);
        this.edges.get(4).ccwpredecessor = this.edges.get(0);
        this.edges.get(4).cwsuccessor = this.edges.get(1);
        this.edges.get(4).ccwsuccessor = this.edges.get(5);
        this.edges.get(4).leftpolygon = this.polygons.get(1);
        this.edges.get(4).rightpolygon = this.polygons.get(3);
        
        this.edges.get(5).cwpredecessor = this.edges.get(4);
        this.edges.get(5).ccwpredecessor = this.edges.get(1);
        this.edges.get(5).cwsuccessor = this.edges.get(2);
        this.edges.get(5).ccwsuccessor = this.edges.get(3);
        this.edges.get(5).leftpolygon = this.polygons.get(2);
        this.edges.get(5).rightpolygon = this.polygons.get(3);
    }

    public void createedges() {
        
        lato e;
        
        e = new lato();
        e.startvertex = this.vertices.get(0);
        e.endvertex = this.vertices.get(1);
        this.edges.add(e);
        
        e = new lato();
        e.startvertex = this.vertices.get(0);
        e.endvertex = this.vertices.get(2);
        this.edges.add(e);
        
        e = new lato();
        e.startvertex = this.vertices.get(0);
        e.endvertex = this.vertices.get(3);
        this.edges.add(e);
        
        e = new lato();
        e.startvertex = this.vertices.get(3);
        e.endvertex = this.vertices.get(1);
        this.edges.add(e);
        
        e = new lato();
        e.startvertex = this.vertices.get(1);
        e.endvertex = this.vertices.get(2);
        this.edges.add(e);
        
        e = new lato();
        e.startvertex = this.vertices.get(2);
        e.endvertex = this.vertices.get(3);
        this.edges.add(e);
        
    }

    public void createpolygons() {
        
        poligono p;
        
        for(int i=0; i<4; i++){
        
            p = new poligono();
            p.edgearoundpolygon = this.edges.get(i);
            this.polygons.add(p);
        }
        
        this.polygons.get(0).generator = this.p1;
        this.polygons.get(1).generator = this.p3;
        this.polygons.get(2).generator = this.p2;
        
        this.p1.polygon = this.polygons.get(0);
        this.p3.polygon = this.polygons.get(1);
        this.p2.polygon = this.polygons.get(2);
    }

    public void createvertices() {
        
        this.vertices.get(0).edgearoundvertex = this.edges.get(0);
        this.vertices.get(1).edgearoundvertex = this.edges.get(3);
        this.vertices.get(2).edgearoundvertex = this.edges.get(4);
        this.vertices.get(3).edgearoundvertex = this.edges.get(5);
        
    }

    public void populatediagram() {
        
        int k = this.qtree.levelcount();
        ArrayList <quadtreenode> nodes;
        quadtreenode node;
        quadtreenode parentnode;
        
        /*per ogni livello dell'albero quaternario*/
        for (int i = 0; i< k; i++){
        
            nodes = this.qtree.getlevel(i);
            int n = nodes.size();
            
            /*se il nodo non è una foglia, allora aggiungi al diagramma
             solo il generatore che non sia lo stesso che ha come riferimento
             il nodo padre perchè questo è stato già aggiunto*/
            for (int j = 0; j < n ; j++){
            
                node = nodes.get(j);
                parentnode = node.parentnode;
                
                if(node.nodetypes != nodelabels.LEAF_NODE){
                
                    if((node.getgenerator(0)!= null)&&(node.getgenerator(0)!= parentnode.getgenerator(0))){
                    
                        addgenerator(node.getgenerator(0), node);
                    }
                }
                
                else {
                
                    for (int m = 0; m < node.getgeneratorcount(); m++){
                    
                        if (node.getgenerator(m)!= parentnode.getgenerator(0))
                            addgenerator(node.getgenerator(m),node);
                    }
                }
            }
        }
    }

    public void addgenerator(vertice p, quadtreenode node) {
        
        poligono closestg;
        closestg = findclosestgenerator(p,node);
        
        if(closestg != null){
        
            poligono closestpolygon;
            closestpolygon = closestg;
            
            ArrayList <vertice> v = new ArrayList <vertice> ();
            
            getedgesandvertices(closestpolygon, null, v);
            
            ArrayList <vertice> T = new ArrayList <vertice> ();
            
            /* per ogni vertice (qijk) che si trova sul boundary 
             del poligono restituito da findclosestgenerator trova quello che minimizza
             il valore di H(i,j,k,p) e aggiungi tale vertice a T */
            
            float minh =(float) 999999.9;
            float hvalue;
            vertice smallestv = null;
            ArrayList <poligono> pg = new ArrayList <poligono> ();
            vertice pi, pj, pk;
            int nv = v.size();
            
            for (int i=0; i<nv; i++){
            
                pg.clear();
                
                getedgesandpolygons(v.get(i), null, pg);
                
                pi = pg.get(0).generator;
                pj = pg.get(1).generator;
                pk = pg.get(2).generator;
                
                if ((pi != null)&&(pj!=null)&&(pk!=null)){
                
                    hvalue = H(pi,pj,pk,p);
                    
                    if (hvalue < minh){
                    
                        minh = hvalue;
                        smallestv = v.get(i);
                    }
                }
            }
            
            T.add(smallestv);
            
            /*espandi il set dei vertici T che formano l'albero
             che verrrà rimosso per far spazio al nuovo poligono di Voronoi*/
            
            expand(T,p,0);
            deleteedges();
            createnewvertices(T,closestpolygon,p);
            
            generators.add(p);
            
            
            T.clear();
            
        }
    }

    /*data una coppia di coordinate in forma di punto, determina il generatore più vicino*/
    public poligono findclosestgenerator(vertice p, quadtreenode node) {
        
        vertice pi = null;
        
        /*utilizza il quaternary inital guess per trovare un candidato 
         generatore per iniziare la ricerca del piu vicino*/
        if (node.nodetypes != nodelabels.LEAF_NODE)
            pi = node.parentnode.getgenerator(0);
        else
            if (node.getgeneratorcount() > 1){
            
                pi = node.getgenerator(0);
                
                if (pi.polygon == null)
                    pi = node.parentnode.getgenerator(0);
            }
            else
                pi = node.parentnode.getgenerator(0);
        
        return getclosestpolygon(pi, p, false);
    }

    public poligono getclosestpolygon(vertice initialguess, vertice p, boolean scalepoints) {
        
        vertice pk = null;
        int i;
        vertice pi, pj = null;
        vertice temp1;
        
        pi = initialguess;
        ArrayList <lato> e = new ArrayList <lato>();
        boolean bfinished = false;
        float mindist = (float) 999999.9;
        while (!bfinished) {
        
            e.clear();
            poligono pgi = pi.polygon;
            getedgesandvertices(pgi, e, null);
            
            /*per ogni lato di quelli ritrovati recupera il 
             poligono che non sia pgi. Trova il poligono che minimizza
             la distanza con p */
            
            float dist;
            poligono otherp;
            lato ed;
            vertice otherg;
            int ne = e.size();
            
            for (i=0; i<ne; i++){
            
                ed=e.get(i);
                if(ed.leftpolygon == pgi)
                    otherp = ed.rightpolygon;
                else
                    otherp = ed.leftpolygon;
                
                otherg = otherp.generator;
                
                if(otherg != null){
                
                    pk = otherg;
                    
                    if (scalepoints == true){
                    
                        temp1 = new vertice();
                        temp1.x = (calcposx(pk.x));
                        temp1.y = (calcposy(pk.y));
                        temp1.w = pk.w;
                    }
                    
                    else 
                        temp1 = pk;
                    
                    dist = getdistance(temp1, p);
                    
                    if (dist <=mindist){
                    
                        mindist = dist;
                        pj = otherg;
                    }
                    
                    
                }
            }
            
            
            if (scalepoints == true) {
            
                temp1 = new vertice();
                temp1.x = (calcposx(pi.x));
                temp1.y = (calcposy(pi.y));
                temp1.w = pi.w;
            }
            
            else
                temp1 = pi;
            
            if (getdistance(temp1, p) <= mindist)
                bfinished = true;
            
            else 
                pi = pj;
            
        }
        
        return pi.polygon;
    }

    public void getedgesandvertices(poligono p, ArrayList<lato> e, ArrayList <vertice> v) {
        
        lato k, kstart;
        
        k = p.edgearoundpolygon;
        kstart = p.edgearoundpolygon;
        
        if (e != null)
            e.add(k);
        boolean bfinished = false;
        
        while (!bfinished){
        
            if (p == k.leftpolygon){
            
                if (v!= null)
                    v.add(k.endvertex);
                
                k = k.cwsuccessor;
            }
            else {
            
                if(v!=null)
                    v.add(k.startvertex);
                
                k = k.cwpredecessor;
            }
            
            if(k == kstart) {bfinished = true;}
            else{
            
                if(e != null)
                    e.add(k);
            }
                
        }
    }

    public void getedgesandpolygons(vertice j, ArrayList <lato> e, ArrayList<poligono> p) {
        
        lato k, kstart;
        
        k = j.edgearoundvertex;
        kstart = j.edgearoundvertex;
        
        if (e!=null)
            e.add(k);
        
        boolean bfinished = false;
        
        while(bfinished == false){
        
            if(j == k.startvertex){
            
                if(p!=null)
                    p.add(k.leftpolygon);
                
                k = k.ccwpredecessor;
            }
            
            else {
            
                if (p!=null)
                    p.add(k.rightpolygon);
                
                k = k.ccwsuccessor;
            }
            
            if (k == kstart){ bfinished = true;}
            else {
            
                if(e!=null)
                    e.add(k);
            }
        }
    }

    
    /*
     * H(Pi, Pj, Pk, Pi) = 0 represents the circle passing through the points
     * Pi, Pj, Pk counterclockwise in this order. If H(Pi, Pj, Pk, P) < 0 then
     * the circle contains point P. If H(Pi, Pj, Pk, P) >= 0 where P is not in
     * {Pi, Pj, Pk}, then the circle is empty*/
    public float H(vertice Pi, vertice Pj, vertice Pk, vertice Pl) {
        
        float J2ijk, J3ijk, J4ijk;
        float Xi, Xj, Xk, Xl, Yi, Yk, Yj, Yl;
        
        float result1;
        
        Xi = Pk.x;  Yk = Pi.y;
	Xj = Pj.x;  Yj = Pj.y;
	Xk = Pi.x;  Yi = Pk.y;
	Xl = Pl.x;  Yl = Pl.y;
        
        J2ijk = ((Yi - Yk) * (((Xj - Xk) * (Xj - Xk)) + ((Yj - Yk) * (Yj - Yk)))) - 
			((Yj - Yk) * (((Xi - Xk) * (Xi - Xk)) + ((Yi - Yk) * (Yi - Yk))));
        
        J3ijk = ((Xi - Xk) * (((Xj - Xk) * (Xj - Xk)) + ((Yj - Yk) * (Yj - Yk)))) - 
			((Xj - Xk) * (((Xi - Xk) * (Xi - Xk)) + ((Yi - Yk) * (Yi - Yk))));
        
        J4ijk = ((Xi - Xk) * (Yj - Yk)) - ((Xj - Xk) * (Yi - Yk));
        
        result1 = ((J2ijk * (Xl - Xk)) - (J3ijk * (Yl - Yk)) + (J4ijk * (((Xl - Xk) * (Xl - Xk)) + ((Yl - Yk) * (Yl - Yk)))));
        
        return result1;
    }

    
    /*per ogni vertice che è connesso da un lato ad uno dei vertici presenti in T,
     aggiungi quel vertice se H(i,j,k,p) <0 e se il vertice non si trova nel circuito esterno
     del grafo dei vertici (sarebbero i vertici all'infinito)*/
    public void expand(ArrayList<vertice> T, vertice p, int startnum) {
        
        lato e;
        vertice startvertex, endvertex, vertextoadd, vint;
        
        vint = T.get(startnum);
        
        ArrayList <lato> eg = new ArrayList <lato> ();
        
        getedgesandpolygons(vint, eg, null);
        int neg = eg.size();
        
        for (int i =0; i<neg; i++){
            
            e=eg.get(i);
            
            if (e != null){
            
                startvertex = e.startvertex;
                endvertex = e.endvertex;
                
                /*verifica che il lato non sia all'infinito */
                if ((startvertex.w == 1) || (endvertex.w == 1)){
                
                    /*verifica che il lato non abbia vertici che siano già in T */
                    if(!((T.contains(startvertex)) && (T.contains(endvertex)))){
                    
                        if(vint == startvertex)
                            vertextoadd = endvertex;
                        else
                            vertextoadd = startvertex;
                        
                        if (vertextoadd.w == 1) {
                        
                            ArrayList <poligono> pg = new ArrayList <poligono>();
                            getedgesandpolygons(vertextoadd, null, pg);
                            
                            vertice pi, pj, pk;
                            
                            /*attenzione a non usare i virtual generator che sono sul circuito esterno*/
                            pi = pg.get(0).generator;
                            pj = pg.get(1).generator;
                            pk = pg.get(2).generator;
                            
                            if((pi!=null)&&(pj!=null)&&(pk!=null)){
                            
                                if(H(pi, pj, pk, p)<0){
                                
                                    T.add(vertextoadd);
                                    expand(T,p,T.size()-1);
                                }
                            }
                        }
                        
                        else
                            vertextoadd = null;
                    }
                    else{
                    
                        /*elimina i lati vecchi contenuti completamente in T */
                        this.deledges.add(e);
                    }
                }
            }
        }
    }

    public void deleteedges() {
        
        lato e;
        int n = this.deledges.size();
        
        for (int i=0; i<n; i++){
            
            e=this.deledges.get(i);
            
            updatepolygonforedgedeletion(e, e.leftpolygon, this.deledges);
            updatepolygonforedgedeletion(e, e.rightpolygon, this.deledges);
            
            e.deleted = true;
        }
        
        this.deledges.clear();
    }

    /*Se il lato da cancellare risulta essere uno degli attributi 'edgearoundpolygon'
     dei poligoni ad esso confinanti allora recupera i lati intorno a tale poligono
     e aggiorna tale attributo */
    public void updatepolygonforedgedeletion(lato deledge, poligono p, ArrayList<lato> deledges) {
        
        ArrayList <lato> ed = new ArrayList <lato>();
        lato e;
        int i;
        
        if (p.edgearoundpolygon == deledge){
        
            getedgesandvertices(p, ed, null);
            int ned = ed.size();
            
            for (i = 0; i < ned; i++){
            
                e = ed.get(i);
                if((e != deledge)&&(!deledges.contains(e))){
                
                    p.edgearoundpolygon = e;
                    break;
                }
            }
        }
        
    }

    /*per ogni lato che connette un vertice in T con uno non in T,
     crea un nuovo vertice su tale lato e dividi il lato in 2 lati (associata a traceedges) */
    public void createnewvertices(ArrayList<vertice> T, poligono closestpolygon, vertice p) {
        
        /*l'array contenente i lati da splittare*/
        ArrayList <lato> modifiededges = new ArrayList <lato> ();
        
        lato e;
        
        int ti;
        
        vertice endv, startv;
        ArrayList <lato> ed = new ArrayList <lato> ();
        int nt = T.size(); 
        
        for(ti=0; ti<nt; ti++){
        
            ed.clear();
            getedgesandpolygons(T.get(ti), ed, null);
            int ned = ed.size();
            
            
            for (int tj=0; tj<ned; tj++){
            
                startv = ed.get(tj).startvertex;
                endv = ed.get(tj).endvertex;
                
                if(!(T.contains(startv) && T.contains(endv)))
                    modifiededges.add(ed.get(tj));
            }
        }
        
        traceedges(modifiededges, closestpolygon, p, T);
        
    }

    public void traceedges(ArrayList<lato> modifiededges, poligono closestpolygon, vertice p, ArrayList<vertice> T) {
        
        lato e, newedge, first, canc;
        
        canc = new lato();
        canc.endvertex = new vertice(0,0,0);
        
        poligono newpolygon = new poligono();
        newpolygon.generator = p;
        p.polygon = newpolygon;
        
        
        /*comincio con i lati che hanno il closest polygon associato al nuovo generatore
         nelle loro right o left polygon properties */
        lato firstedge = null;
        lato secondedge = null;
        
        int i;
        int firstindex = 0;
        int secondindex = 0;
        int n = modifiededges.size();
        
        for (i=0; i<n; i++){
        
            e = modifiededges.get(i);
            if(e.leftpolygon.equals(closestpolygon)){
            
                if (firstedge == null){
                
                    firstedge = e;
                    firstindex = i;
                }
                
                else if (firstedge != null){
                
                    secondedge = e;
                    secondindex = i;
                }
                
                if ((firstedge != null) && (secondedge != null))
                    break;
            }
            
            else if (e.rightpolygon.equals(closestpolygon)){
            
                if (secondedge == null){
                
                    secondedge = e;
                    secondindex = i;
                }
                
                else if (secondedge != null){
                
                    firstedge = e;
                    firstindex = i;
                }
                
                if ((firstedge != null)&&(secondedge != null))
                    break;
            }
        }
        
        ArrayList <lato> newedges = new ArrayList <lato>();
        
        newedge = createfirstnewedge(firstedge,secondedge,closestpolygon,p,newpolygon);
        
        if (newedge == null)
            return;
        
        ArrayList <lato> atemp = sortinitialedges(newedge,p,firstedge,secondedge);
        
        if (atemp != null){
        
            int temp = secondindex;
            secondindex = firstindex;
            firstindex = temp;
            
            firstedge = atemp.get(0);
            secondedge = atemp.get(1);
        }
        
        modifiededges.set(secondindex, null);
        
        first = firstedge;
        
        newedges.add(newedge);
        
        newpolygon.edgearoundpolygon = newedge;
        
        ArrayList <lato> modedges = new ArrayList<lato>();
        
        modedges.add(firstedge);
        
        modedges.add(secondedge);
        
        boolean bfinished = false;
        
        poligono lastbounded = closestpolygon;
        
        poligono nextpolygon;
        
        while (!bfinished){
        
            vertice prevstart = newedges.get(newedges.size()-1).endvertex;
            
            if (secondedge.leftpolygon == lastbounded)
                nextpolygon = secondedge.rightpolygon;
            else
                nextpolygon = secondedge.leftpolygon;
            
            lastbounded = nextpolygon;
            
            int nm = modifiededges.size();
            
            /*cerca il lato che condivide un poligono diverso dall'ultimo bounded con il secondedge*/
            for (i=0; i<nm; i++){
            
                e = modifiededges.get(i);
                
                if (e == null)
                    continue;
                
                if ((e.leftpolygon == nextpolygon)||(e.rightpolygon == nextpolygon)){
                
                    secondindex = i;
                    firstedge = secondedge;
                    secondedge = e;
                    
                    break;
                }
            }
            
            modifiededges.set(secondindex, null);
            
            /*abbiamo chiuso il loop confinando il sottoalbero contenuto in T*/
            if(secondedge == first){
            
                newedge = new lato();
                newedge.startvertex = prevstart;
                newedge.endvertex = newedges.get(0).startvertex;
                newedge.leftpolygon = newpolygon;
                newedge.rightpolygon = nextpolygon;
                newedges.add(newedge);
                
                bfinished = true;
                
            }
            
            else {
            
                newedge = createnewedge(secondedge,nextpolygon,p,newpolygon);
                newedge.startvertex = prevstart;
                
                newedges.add(newedge);
                modedges.add(secondedge);
            }
        }
        
        for (i=0; i<newedges.size(); i++){
        
            e = newedges.get(i);
            edges.add(e);
        }
        
        
        
        modifyedges(newedges,modedges, T, newpolygon);
        
        
        polygons.add(newpolygon);
        
    }

    /*proietta una linea tra il generatore di poli e p e trova le coordinate 
     dei punti in cui la bisettrice perpendicolare a tale linea interseca firstedge.
     a questo punto traccia un lato tra di essi*/
    public lato createfirstnewedge(lato firstedge, lato secondedge, poligono poli, vertice p, poligono newpolygon) {
        
        vertice pi = poli.generator;
        
        float x1, x2, y1, y2;
        x1 = p.x; x2 = pi.x;
        y1 = p.y; y2 = pi.y;
        
        vertice mid = new vertice((float)((x1 + x2) / 2.0), (float)((y1 + y2) / 2.0), 0);
        vertice bi = new vertice((float)((y1 - y2)), (float)(0-(x1 - x2)),0);
        
        float px1, px2, py1, py2;
        px1 = mid.x;
	py1 = mid.y;
	px2 = mid.x + bi.x;
	py2 = mid.y + bi.y;
        
        lato newedge = new lato();
        
        vertice vtemp = getintersection (firstedge,px1,py1,px2,py2);
        
        if (vtemp == null)
            return null;
        
        vertice v = new vertice(vtemp.x,vtemp.y,1);
        
        newedge.startvertex = v;
        newedge.startvertex.edgearoundvertex = newedge;
        
        vtemp = getintersection(secondedge,px1,py1,px2,py2);
        
        if (vtemp == null)
            return null;
        
        vertice v2 = new vertice(vtemp.x, vtemp.y,1);
        
        newedge.endvertex = v2;
        newedge.endvertex.edgearoundvertex = newedge;
        
        newedge.rightpolygon = poli;
        newedge.leftpolygon = newpolygon;
        
        return newedge;
        
    }

    /*dato un lato e una generica retta, restituisco il punto di intersezione */
    public vertice getintersection(lato e, float xa, float ya, float xb, float yb) {
        
        float x1 = xa; float y1 = ya;
        float x2 = xb; float y2 = yb;
        float x3,x4,y3,y4;
        
        if(e.startvertex.w == 0){
        
            x3 = e.endvertex.x + e.startvertex.x;
            x4 = e.endvertex.x;
            y3 = e.endvertex.y + e.startvertex.y;
            y4 = e.endvertex.y;
        }
        
        else if (e.endvertex.w == 0){
        
            x3 = e.startvertex.x;
            x4 = e.startvertex.x + e.endvertex.x;
            y3 = e.startvertex.y;
            y4 = e.startvertex.y + e.endvertex.y;
        }
        
        else {
        
            x3 = e.startvertex.x;
            x4 = e.endvertex.x;
            y3 = e.startvertex.y;
            y4 = e.endvertex.y;
        }
        
        float nma , nmb;
        float dm;
        float ua, ub;
        
        nma = (((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3)));
	nmb = (((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)));
	dm = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
        
        if ((dm == 0) && (nma == 0)){}
        else if (dm == 0){}
        else{
        
            ua = nma / dm;
            ub = nmb / dm;
            
            float xv, yv;
            
            xv = x1 + (ua * (x2-x1));
            yv = y1 + (ua * (y2-y1));
            
            return new vertice(xv,yv,0);
        }
        
        return null;
        
    }

    /*quando si crea il primo lato di voronoi, dobbiamo determinare su quale dei 
     due lati esistenti del nuovo lato cadrà lo startvertex */
    public ArrayList<lato> sortinitialedges(lato newedge, vertice p, lato firstedge, lato secondedge) {
        
        vertice v1,v2;
        
        v1 = newedge.startvertex;
        v2 = newedge.endvertex;
        
        ArrayList <lato> result1 = null;
        
        float itest = (p.y - v1.y) * (v2.x - v1.x) - 
			(p.x - v1.x) * (v2.y - v1.y);
        
        if (itest>0){
        
            result1 = new ArrayList <lato>();
            newedge.startvertex = v2;
            newedge.endvertex = v1;
            
            result1.add(secondedge);
            result1.add(firstedge);
        }
        
        return result1;
    }

    /*proietta una linea tra il generatore di poli e p e trova le coordinate 
     dei punti in cui la bisettrice perpendicolare a tale linea interseca firstedge.
     a questo punto traccia un lato tra di essi*/
    public lato createnewedge(lato secondedge, poligono poli, vertice p, poligono newpolygon) {
        
        vertice pi = poli.generator;
        
        float x1, x2, y1, y2;
	x1 = p.x; x2 = pi.x;
	y1 = p.y;  y2 = pi.y;
        
        vertice mid = new vertice((float)((x1 + x2) / 2.0), (float)((y1 + y2) / 2.0), 0);
        vertice bi = new vertice((float)((y1 - y2)),(float)(0-(x1 - x2)),0);
        
        float px1, px2, py1, py2; // Segment of the bisector
	px1 = mid.x;
	py1 = mid.y;
	px2 = mid.x + bi.x;
	py2 = mid.y + bi.y;
        
        lato newedge = new lato();
        
        vertice v;
        
        v = getintersection(secondedge, px1, py1, px2, py2);
        v.w = 1;
        
        newedge.endvertex = v;
        newedge.endvertex.edgearoundvertex = newedge;
        
        newedge.rightpolygon = poli;
        newedge.leftpolygon = newpolygon;
        
        return newedge;
    }

    /*dato il set di lato che devono essere divisi in due e dato il set dei nuovi 
     lati creati, spezziamo i lati modificati ed eliminiamo il sottoalbero contenuto in T*/
    public void modifyedges(ArrayList<lato> newedges, ArrayList<lato> modedges, ArrayList<vertice> T, poligono newpolygon) {
        
        lato emod = null;
        lato enew = null;
        lato e = null;
        
        int i; 
        
        for(i=0; i<modedges.size(); i++){
        
            enew = newedges.get(i);
            emod = modedges.get(i);
            
            if(T.contains(emod.startvertex)){
            
                emod.startvertex = enew.startvertex;
                emod.ccwpredecessor = enew;
                
                if(i>0)
                    emod.cwpredecessor = newedges.get(i-1);
                else
                    emod.cwpredecessor = newedges.get(newedges.size()-1);
                
            }
            
            else if(T.contains(emod.endvertex)){
            
                emod.endvertex = enew.startvertex;
                emod.ccwsuccessor = enew;
                
                if (i>0)
                    emod.cwsuccessor = newedges.get(i-1);
                else
                    emod.cwsuccessor = newedges.get(newedges.size()-1);
            }
        }
        
        /*aggiorna le proprietà successore- predecessore dei lati appena creati*/
        int nen = newedges.size();
        
        for (i=0; i<nen; i++){
        
            e = newedges.get(i);
            e.cwpredecessor = modedges.get(i);
            
            if (i>0)
                e.ccwpredecessor = newedges.get(i-1);
            else
                e.ccwpredecessor = newedges.get(newedges.size()-1);
            
            if(i == (newedges.size() - 1)){
            
                e.ccwsuccessor = modedges.get(0);
                e.cwsuccessor = newedges.get(0);
            }
            
            else{
            
                e.ccwsuccessor = modedges.get(i+1);
                e.cwsuccessor = newedges.get(i+1);
            }
        }
    }

    /*prepara i lati per l'output da ritornare al client*/
    public void printdiagram() {
        
        vertice startV, endV;
        float x1,x2,y1,y2;
        Line2D line;
        for(int i =0; i<edges.size(); i++){
        
            if (edges.get(i) != null){
                
                /*aggiungi solo i lati non eliminati e considera quelli
                 che non hanno la chiusura all'infinito */
		if (edges.get(i).deleted == false) {
                    
                    startV = edges.get(i).startvertex;
                    endV = edges.get(i).endvertex;
					
                    if ((startV.w == 1) && (endV.w == 1))
                    {
                        
			x1 = calcposx(startV.x);
			y1 = calcposy(startV.y);
			x2 = calcposx(endV.x);
			y2 = calcposy(endV.y);
			
                        line = new Line2D.Float(x1,y1,x2,y2);
                        
                        this.result.getShapes().add(line);

                    }
                }
            }
            
            /*
            System.out.println("Lato n: "+i+"  :");
            System.out.println("startvertex : x--> "+edges.get(i).startvertex.x+" , y--> "+edges.get(i).startvertex.y);
            System.out.println("endvertex : x--> "+edges.get(i).endvertex.x+" , y--> "+edges.get(i).endvertex.y);
            * */
            
        }
    }
   
    




}//end voronoidiagram
